package Binary;

import com.sun.source.tree.Tree;

public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;


        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public void insert(int key){
        if(root==null){
            root=new TreeNode(key);
            return;
        }
        TreeNode node=new TreeNode(key);
        TreeNode prv=null;
        TreeNode cur=root;
        while(cur!=null){
            if(key<cur.val){
                prv=cur;
                cur=cur.left;
            }else if(key> cur.val){
                prv=cur;
                cur=cur.right;
            }else {
                return;
            }
        }
        if(prv.val>key){
            prv.left=node;
        }else{
            prv.right=node;
        }



    }

    public boolean search(int val){
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val>val){
                cur=cur.left;
            }else if (cur.val<val){
                cur=cur.right;
            }else {
                return true;
            }
        }
    return false;
    }

    public  void remove(int val){
        if(root==null){
            return;
        }

TreeNode prv=null;
TreeNode cur=root;
while(cur!=null){
    if(cur.val>val){
        prv=cur;
        cur=cur.left;
    }else if(cur.val<val){
        prv=cur;
        cur=cur.right;
    }else {
        break;
    }
}
if(cur==null){
    return;
}
removeNode(prv,cur);
    }

    private void removeNode(TreeNode prv,TreeNode cur){
        //要删除节点的左子树为空
if(cur.left==null){
    //节点为根节点
    if(cur==root){
        root=cur.right;
    }else if(cur==prv.right){
        prv.right=cur.right;
    } else{
        prv.left=cur.right;
    }
}

//要删除节点的右子树为空
        else   if(cur.right==null){
            if(cur==root){
                root=cur.left;
            } else if (cur==prv.left) {
                prv.left=cur.left;
            }else {
                prv.right=cur.left;
            }
        }
        //要删除的节点两边都不为空
        else {
            TreeNode p=cur;
    TreeNode c=cur.left;
    while(c.right!=null){
        p=c;
        c=c.right;
    }
swap(c,cur);
   if(c==p.left){
       p.left=c.left;
   }
   if(c==p.right){
       p.right=c.left;
   }
        }
    }

private void swap(TreeNode v1,TreeNode v2){
        int tmp= v1.val;
        v1.val=v2.val;
        v2.val=tmp;
}


}
